//1.挨个比较（好理解）
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int s_size = s.size();
        int p_size = p.size();
        if(s_size < p_size)
            return {};
        vector<int> ret;
        vector<int> c_s(26); //存储p的字母个数
        vector<int> c_p(26);
        for(int i=0;i<p.size();++i) {
            c_s[s[i]-'a']++;
            c_p[p[i]-'a']++;
        }
        if(c_s == c_p)
            ret.push_back(0);

        for(int i=0;i<s_size-p_size;++i) {
            c_s[s[i]-'a']--;
            c_s[s[i+p_size]-'a']++;
            if(c_s == c_p)
                ret.push_back(i+1);
        }

        return ret;

    }
};

// 2.differ统计不同数字个数--时间复杂度更优
/*
定义一个滑动窗口，先把s的前pLen个数组统计下，然后减去p的前pLen个数组。
起始的窗口在s开头。举例子，假如s="cbaebabacd",p="abe"
count数组的前三个元素a,b,c起始都为1（除非对应的p位置也是"abc"，这样count数组的前三个元素a,b,c起始都为1-1=0）
同样的，s的后sLen-pLen个元素不是0就是-1（-1是 对应p[i]位置减的）
differ统计不同的数字，对应count[i]的值-----》count[i]==0是刚刚好，1是多了，-1是缺了
differ为0是不多不少，加入索引到ans

然后窗口向右移一位，则当前起始位置的count[i]要减去，末尾位置的count[i+pLen]要加上
左右位置变化导致differ变化，左边界：  
                        (1)  左边界=1，1-1=0，这个多余的元素走了，differ--；
                        (2)  左边界=0，0-1=0，缺少这个元素了，本来阴阳平衡，所以differ++；
                          右边界：  
                        (1)  右边界=0，0+1=1，多余的元素来了，differ++；
                        (2)  右边界=-1，-1+1=0，缺少这个元素来了，，所以differ--；
*/


class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) 
            return vector<int>();
        
        vector<int> ans;
        vector<int> count(26);
        for (int i = 0; i < pLen; ++i) {
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) 
            if (count[j] != 0)    ++differ;
            

        if (differ == 0) 
            ans.push_back(0);
        

        for (int i = 0; i < sLen - pLen; ++i) {
            if (count[s[i] - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s[i] - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s[i] - 'a'];

            if (count[s[i + pLen] - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s[i + pLen] - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s[i + pLen] - 'a'];
            
            if (differ == 0) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};
/*
ai总结
✅ 你说的核心逻辑拆解
1. 初始化阶段
“先把 s 的前 pLen 个字符统计下，然后减去 p 的前 pLen 个字符”

完全正确！这一步构造了一个差分数组 count[26]，表示：

count[i]=窗口中字符 i 的频次−p 中字符 i 的频次
2. count[i] 的含义
你说：

count[i] == 0 → 阴阳平衡，刚刚好 ✅

count[i] == 1 → 多了 ✅

count[i] == -1 → 缺了 ✅

这正是我们用 differ 来统计的：有多少个字符频次不平衡。

3. differ 的含义
你说：“differ 为 0 是不多不少，加入索引”

完全正确！当 count[i] == 0 对所有 i 成立时，说明窗口和 p 完全匹配 → 是异位词。

4. 滑动窗口更新逻辑
你说：

“窗口向右移一位，则当前起始位置的 count[i] 要减去，末尾位置的 count[i+pLen] 要加上”

这就是：

左边界字符移出 → count[out] -= 1

右边界字符加入 → count[in] += 1

然后根据变化前后是否跨越 0 来更新 differ。

✅ 你列出的四种情况分析
我们来逐条验证你写的左右边界变化逻辑：

🔹 左边界移出字符（count[c] -= 1）
(1) 原来是 1 → 变成 0
“多余的元素走了，differ--” ✅

原来是多了一个字符，现在刚好 → 减少一个不匹配 → differ--

(2) 原来是 0 → 变成 -1
“缺少这个元素了，本来阴阳平衡，所以 differ++” ✅

原来是平衡，现在少了 → 增加一个不匹配 → differ++

🔹 右边界加入字符（count[c] += 1）
(1) 原来是 0 → 变成 1
“多余的元素来了，differ++” ✅

原来平衡，现在多了 → 增加一个不匹配 → differ++

(2) 原来是 -1 → 变成 0
“缺少的元素来了，所以 differ--” ✅

原来少了，现在刚好 → 减少一个不匹配 → differ--

*/



